home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / incl / LEDA / impl / range_tree1.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  2.7 KB  |  103 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  range_tree1.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef RANGE_TREE1_H
  17. #define RANGE_TREE1_H
  18.  
  19. #include <LEDA/impl/genra_tree.h>
  20.  
  21. //
  22. // D-Dimensional Range Trees
  23. // -------------------------------------
  24. //
  25. //
  26. // exchangable underlying data structure
  27. //
  28. // 7/92, M.Paul
  29. //
  30.  
  31.  
  32.  
  33. template<class keytype, class inftype>
  34. class range_tree1 : public genra_tree
  35. {
  36.  
  37.   GenPtr* Conv( keytype k[] ) const        // convert an array
  38.   { register int d;
  39.     GenPtr* ca = new GenPtr[dim1+1] ;
  40.     for( d=dim1; d>=0; d-- )
  41.       ca[d] = Convert(k[d]) ;
  42.     return ca ;
  43.   };
  44.  
  45.   int r_cmp( GenPtr x, GenPtr y ) const
  46.     { return compare(ACCESS(keytype,x),ACCESS(keytype,y)); }
  47.   void r_copy_key( GenPtr*& x ) const
  48.     { for( int d=dim1; d>=0; d-- ) x[d]=Copy(ACCESS(keytype,x[d])); }
  49.   void r_copy_inf( GenPtr& x ) const { x=Copy(ACCESS(inftype,x)); }
  50.   void r_clear_key( GenPtr*& x ) const
  51.     { for( int d=dim1; d>=0; d-- ) Clear(ACCESS(keytype,x[d])); }
  52.   void r_clear_inf( GenPtr& x ) const { Clear(ACCESS(inftype,x)); }
  53.  
  54.   public:
  55.  
  56.     void r_print_key( GenPtr* x ) const
  57.       { cout << "( ";
  58.     for( int d=dim1; d>=0; d--,cout << " " )
  59.       cout << (keytype) ACCESS(keytype,x[d]);
  60.         cout << ") "; }
  61.     void r_print_inf( GenPtr x ) const
  62.       { cout << (inftype) ACCESS(inftype,x); }
  63.  
  64.     LEDA_MEMORY( range_tree1 ) ;
  65.  
  66.     genra_tree* create_genra_tree( int d )
  67.       { return new range_tree1(d); }
  68.  
  69.     range_tree1( int d = 2 ) { dim1=d-1; }
  70.  
  71.     virtual void clear() { genra_tree::clear(); }
  72.     ~range_tree1() { clear(); }
  73.  
  74.     virtual int dimension() const { return genra_tree::dimension(); }
  75.     virtual int size() const { return genra_tree::size(); }
  76.     virtual int empty() const { return genra_tree::empty(); }
  77.  
  78.     virtual void query( keytype low[], keytype high[], list<GenPtr>& lgi) const
  79.       { GenPtr* l = Conv(low); GenPtr* h = Conv(high);
  80.         genra_tree::query(l,h,lgi);
  81.       }
  82.  
  83.     virtual grt_item lookup( keytype key[] ) const
  84.       { GenPtr* k = Conv(key); return genra_tree::lookup(k); }
  85.  
  86.     virtual list<GenPtr> all_items() const { return genra_tree::all_items(); }
  87.  
  88.     virtual grt_item insert( keytype key[], inftype inf )
  89.       { GenPtr* k = Conv(key) ;
  90.         grt_item gi = genra_tree::insert(k,Convert(inf));
  91.     return gi ;
  92.       }
  93.  
  94.     virtual void del( keytype key[] )
  95.       { GenPtr* k = Conv(key); genra_tree::del(k); }
  96.  
  97.     virtual void del_item( grt_item gi ) { genra_tree::del_item(gi); }
  98. } ;
  99.  
  100.  
  101.  
  102. #endif
  103.